package com.wfm.alg;

import org.junit.Test;

/**
 * https://blog.csdn.net/zearot/article/details/52280189
 * https://blog.csdn.net/zearot/article/details/48299459
 * https://lfool.github.io/LFool-Notes/algorithm/%E7%BA%BF%E6%AE%B5%E6%A0%91%E8%AF%A6%E8%A7%A3.html
 * https://leetcode.cn/problems/my-calendar-i/solutions/1646079/by-lfool-xvpv/
 */
public class P线段树 {
    //===================线段树的数组实现==============
    public static class SegTreeByNum{
        int[] segmentTree;//i从0开始的话，i的左节点=2i+1,i的右节点=2i+2
        int n;
        int[] nums;
        public SegTreeByNum(int[] nums){
            this.nums=nums; // 原数组的引用
            n=nums.length;
            segmentTree=new int[n*4];//// *4是因为右孩子能到2n+2,*3的话，当n=1的时候，数组长度不够保存的，所以只能*4才能保存下所有
            buildTree(0,0,n-1);
        }

        private void buildTree(int node,int l,int r) {
            if(l==r){
                segmentTree[node]=nums[l];
                return;
            }
            int m = l+(r-l)/2;
            buildTree(node*2+1,l,m);//建立node的左孩子树
            buildTree(node*2+2,m+1,r);// 建立node的右孩子树
            segmentTree[node]=segmentTree[node*2+1]+segmentTree[node*2+2];
        }

        // 在以node为节点，区间为[l,r]的线段树里设置index下标值变成val
        public void update(int index,int val,int node,int l,int r){
            if(l==r){
                segmentTree[node]=val;
                return;
            }
            int m = l+(r-l)/2;
            if(index<=m){
                update(index,val,node*2+1,l,m);
            }else {
                update(index,val,node*2+2,m+1,r);
            }
            segmentTree[node]=segmentTree[node*2+1]+segmentTree[node*2+2];
        }

        // 以nod为节点，区间为[l,r]的树下，累加区间为[left，right]的和
        public int query(int left,int right,int node,int l,int r){
            if(left==l&&right==r){
                return segmentTree[node];
            }
            int m = l+(r-l)/2;
            if(right<=m){
                return query(left,right,node*2+1,l,m);
            }else if(left>m){
                return query(left,right,node*2+2,m+1,r);
            }else{
                return query(left,m,node*2+1,l,m)+query(m+1,right,node*2+2,m+1,r);
            }
        }
    }

    //===================线段树的链表实现==============
    public static class SegTreeByLinked{
        Node root = new Node();
        int[] nums;
        public SegTreeByLinked(int[] nums){
            this.nums=nums;
            buildTree(root,0,nums.length-1);
        }
        public void buildTree(Node node, int start, int end) {
            // 到达叶子节点
            if (start == end) {
                node.val = nums[start];
                return ;
            }
            int mid = (start + end) >> 1;
            buildTree(node.left, start, mid);
            buildTree(node.right, mid + 1, end);
            // 向上更新
            pushUp(node);
        }

        public void update(int left,int right,int val,Node node, int l ,int r){
            if(left<=l&&right>=r){
                node.val+=(r-l+1)*val;
                return;
            }
            int m = l+(r-l)/2;
            if(right<=m){
                update(left,right,val,node.left,l,m);
            }else if(left>m){
                update(left,right,val,node.right,m+1,r);
            }else{
                update(left,m,val,node.left,l,m);
                update(m+1,right,val,node.right,m+1,r);
            }
            pushUp(node);
        }

        public int query(int left,int right,Node node ,int l,int r){
            if(left<=l&&right>=r){
                return node.val;
            }
            int m = l+(r-l)/2;
            if(right<=m){
                return query(left,right,node.left,l,m);
            }else if(left>m){
                return query(left,right,node.right,m+1,r);
            }else{
                return query(left,m,node.left,l,m)+query(m+1,right,node.right,m+1,r);
            }
        }

        private void pushUp(Node node) {
            node.val = node.left.val + node.right.val;
        }


        static class Node{
            Node left;
            Node right;
            int val;
        }
    }
    //===================动态线段树+懒加载==============

    /**
     * SumSum1系列：update对某个区间【累加】val，查询的时候查区间的【累加值】
     *       update：val+=val*num    pushDown:node.left.val+=node.add*leftNum  node.left.val+=node.add*rightNum  query：+
     *               add+=val                 node.right.add+=node.val node.right.add+=node.add
     * SumMax2系列：update对某个区间【累加】val，查询的时候，查询区间的【最值】
     *       update：val+=val    pushDown:node.left.val+=node.add  node.left.val+=node.add                       query：Max
     *               add+=add                 node.right.add+=node.val node.right.add+=node.add
     * SetSum3系列，update对某个区间【设置】val，查询的时候查询区间的【累加值】
     *       update：val=val*num    pushDown:node.left.val=node.add*leftNum  node.left.val=node.add*rightNum    query：+
     *               add=val                 node.right.add=node.val node.right.add=node.add
     * SetMax4系列，update对某个区间【设置】val，查询的时候查询区间的【最值】
     *       update：val=val    pushDown:node.left.val=node.add  node.left.val=node.add
     *       query：Max
     *               add=val                 node.right.add=node.val node.right.add=node.add
     */
    public static class SegTreeDynamic{
        public static class Node {
            Node left, right;
            int val, add;
        }

        public int N = (int) 1e9;
        public Node root = new Node();
//======SumSum1系列=============================================================================
        // 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val
        public void updateSumSum(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val += (end - start + 1) * val;
                node.add += val;
                return ;
            }
            int mid = (start + end) >> 1;
            pushDown(node, mid - start + 1, end - mid);

            if(r<=mid){
                updateSumSum(node.left,start,mid,l,r,val);
            }else if(l>mid){
                updateSumSum(node.right,mid+1,end,l,r,val);
            }else {
                updateSumSum(node.left,start,mid,l,mid,val);
                updateSumSum(node.right,mid+1,end,mid+1,r,val);
            }
            node.val = node.left.val + node.right.val;
        }

        // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
        public int querySumSum(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            int mid = (start + end) >> 1, ans = 0;
            pushDown(node, mid - start + 1, end - mid);
            if(r<=mid){
                ans =  querySumSum(node.left,start,mid,l,r);
            }else if(l>mid){
                ans = querySumSum(node.right,mid+1,end,l,r);
            }else {
                ans= querySumSum(node.left,start,mid,l,mid)+
                        querySumSum(node.right,mid+1,end,mid+1,r);
            }
            return ans;
        }

        private void pushDown(Node node, int leftNum, int rightNum) {
            // 动态开点 如果节点没有左右子节点，先开个没有值的节点
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return ;
            node.left.val += node.add * leftNum;
            node.right.val += node.add * rightNum;
            // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
            node.left.add += node.add;
            node.right.add += node.add;
            node.add = 0;
        }

//======SumMax2系列=============================================================================
        // 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val
        public void updateSumMax(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val += val;
                node.add += val;
                return ;
            }
            int mid = (start + end) >> 1;
            pushDown1(node);
            if(r<=mid){
                updateSumMax(node.left,start,mid,l,r,val);
            }else if(l>mid){
                updateSumMax(node.right,mid+1,end,l,r,val);
            }else {
                updateSumMax(node.left,start,mid,l,mid,val);
                updateSumMax(node.right,mid+1,end,mid+1,r,val);
            }
            node.val = Math.max(node.left.val , node.right.val);
        }

        // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
        public int querySumMax(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            int mid = (start + end) >> 1, ans = 0;
            pushDown1(node);
            if(r<=mid){
                ans =  querySumMax(node.left,start,mid,l,r);
            }else if(l>mid){
                ans = querySumMax(node.right,mid+1,end,l,r);
            }else {
                ans=Math.max(querySumMax(node.left,start,mid,l,mid),
                        querySumMax(node.right,mid+1,end,mid+1,r));
            }
            return ans;
        }

        private void pushDown1(Node node) {
            // 动态开点 如果节点没有左右子节点，先开个没有值的节点
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return ;
            node.left.val += node.add;
            node.right.val += node.add;

            node.left.add += node.add;
            node.right.add += node.add;
            node.add = 0;
        }

//======SetSum3系列=============================================================================
        // node.val代表该节点下所有子节点的和
        // node.add代表该节点下所有子节点下推时应该加多少
        // 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val
        public void updateSetSum(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val = (end-start+1)*val;
                node.add = val;
                return ;
            }
            int mid = (start + end) >> 1;
            pushDown2(node,mid-start+1,end-mid);
            if(r<=mid){
                updateSetSum(node.left,start,mid,l,r,val);
            }else if(l>mid){
                updateSetSum(node.right,mid+1,end,l,r,val);
            }else {
                updateSetSum(node.left,start,mid,l,mid,val);
                updateSetSum(node.right,mid+1,end,mid+1,r,val);
            }
            node.val = node.left.val +node.right.val;
        }

        // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
        public int querySetSum(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            int mid = (start + end) >> 1, ans = 0;
            pushDown2(node,mid-start+1,end-mid);
            if(r<=mid){
                ans =  querySetSum(node.left,start,mid,l,r);
            }else if(l>mid){
                ans = querySetSum(node.right,mid+1,end,l,r);
            }else {
                ans= querySetSum(node.left,start,mid,l,mid)+
                        querySetSum(node.right,mid+1,end,mid+1,r);
            }
            return ans;
        }

        private void pushDown2(Node node,int leftNum,int rightNum) {
            // 动态开点 如果节点没有左右子节点，先开个没有值的节点
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return ;
            node.left.val = node.add*leftNum;
            node.right.val = node.add*rightNum;

            node.left.add = node.add;
            node.right.add = node.add;
            node.add = 0;
        }

//======SetMax4系列=============================================================================
        // node.val代表该节点下所有子节点的和
        // node.add代表该节点下所有子节点下推时应该加多少
        // 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val
        public void updateSetMax(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val = val;
                node.add = val;
                return ;
            }
            int mid = (start + end) >> 1;
            pushDown3(node);
            if(r<=mid){
                updateSetMax(node.left,start,mid,l,r,val);
            }else if(l>mid){
                updateSetMax(node.right,mid+1,end,l,r,val);
            }else {
                updateSetMax(node.left,start,mid,l,mid,val);
                updateSetMax(node.right,mid+1,end,mid+1,r,val);
            }
            node.val = Math.max(node.left.val ,node.right.val);
        }

        // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
        public int querySetMax(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            int mid = (start + end) >> 1, ans = 0;
            pushDown3(node);
            if(r<=mid){
                ans =  querySetMax(node.left,start,mid,l,r);
            }else if(l>mid){
                ans = querySetMax(node.right,mid+1,end,l,r);
            }else {
                ans=Math.max(querySetMax(node.left,start,mid,l,mid),
                        querySetMax(node.right,mid+1,end,mid+1,r));
            }
            return ans;
        }

        private void pushDown3(Node node) {
            // 动态开点 如果节点没有左右子节点，先开个没有值的节点
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return ;
            node.left.val = node.add;
            node.right.val = node.add;

            node.left.add = node.add;
            node.right.add = node.add;
            node.add = 0;
        }

        public void pt(P线段树.SegTreeDynamic tree,int n ){
            for (int i = 0; i <= n; i++) {
                System.out.println("====>"+tree.querySumMax(tree.root, 0, tree.N, i,i));
            }
        }
    }

    @Test
    public void test(){
        SegTreeByNum segTreeByNum = new SegTreeByNum(new int[]{0,1,2,3,4});
        System.out.println(segTreeByNum.query(2, 4,0,0,4));
    }

    @Test
    public void testSegTreeByLinked(){
        SegTreeByLinked segTree = new SegTreeByLinked(new int[]{0,1,2,3,4});

        segTree.update(2,2,3,segTree.root,0,4);
        int query = segTree.query(0, 4, segTree.root, 0, 4);
        System.out.println(query);//3
        segTree.update(0,0,1,segTree.root,0,4);
        int query1 = segTree.query(0, 4, segTree.root, 0, 4);
        System.out.println(query1);//4
        segTree.update(1,1,2,segTree.root,0,4);
        int query2 = segTree.query(0, 4, segTree.root, 0, 4);
        System.out.println(query2);//6
        segTree.update(3,3,4,segTree.root,0,4);
        System.out.println(segTree.query(0,4,segTree.root,0,4));//10
        segTree.update(4,4,5,segTree.root,0,4);
        System.out.println(segTree.query(0,4,segTree.root,0,4));//15

    }

    @Test
    public void testSegTreeDynamic(){
        SegTreeDynamic segTree = new SegTreeDynamic();


        segTree.updateSumSum(segTree.root,0,segTree.N,2,2,3);//x x 3 x x x x
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 2, 2));//3
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 2, 3));//3
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 1, 2));//3
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 0, 1));//0


        segTree.updateSumSum(segTree.root,0,segTree.N,0,0,1);//1 x 3 x x x x
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N,0, 0));//1

        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 0, 3));//4

        segTree.updateSumSum(segTree.root,0,segTree.N,1,1,2);//1 2 3 x x x x
        System.out.println(segTree.querySumSum(segTree.root, 0, segTree.N, 0, 4));//6

        segTree.updateSumSum(segTree.root,0,segTree.N,3,3,4);//1 2 3 4 x x x
        System.out.println(segTree.querySumSum(segTree.root,0,segTree.N,0,4));//10

        segTree.updateSumSum(segTree.root,0,segTree.N,0,4,1);//2 3 4 5 1 x x
        System.out.println(segTree.querySumSum(segTree.root,0,segTree.N,0,4));//15
    }
    @Test
    public void testSegTreeDynamic1(){
        SegTreeDynamic segTree = new SegTreeDynamic();
        segTree.updateSumMax(segTree.root,0,segTree.N,2,2,3);//x x 3 x x x x
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 2, 2));//3
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 2, 3));//3
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 1, 2));//3
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 0, 1));//0

        segTree.updateSumMax(segTree.root,0,segTree.N,0,0,1);//1 x 3 x x x x
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N,0, 0));//1

        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 0, 3));//3

        segTree.updateSumMax(segTree.root,0,segTree.N,1,1,2);//1 2 3 x x x x
        System.out.println(segTree.querySumMax(segTree.root, 0, segTree.N, 0, 4));//3

        segTree.updateSumMax(segTree.root,0,segTree.N,3,3,4);//1 2 3 4 x x x
        System.out.println(segTree.querySumMax(segTree.root,0,segTree.N,0,4));//4

        segTree.updateSumMax(segTree.root,0,segTree.N,0,4,1);//2 3 4 5 1 x x
        System.out.println(segTree.querySumMax(segTree.root,0,segTree.N,0,4));//5
        System.out.println(segTree.querySumMax(segTree.root,0,segTree.N,4,5));//1
    }
    @Test
    public void testSegTreeDynamic2(){
        SegTreeDynamic segTree = new SegTreeDynamic();
        segTree.updateSetSum(segTree.root, 0, segTree.N, 5, 7 - 1, 1);
        segTree.pt(segTree,6);
//        segTree.updateSetSum(segTree.root,0,segTree.N,2,2,3);//x x 3 x x x x
//        segTree.pt(segTree,6);
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 2, 2));//3
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 2, 3));//3
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 1, 2));//3
//
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 0, 1));//0
//
//        segTree.updateSetSum(segTree.root,0,segTree.N,0,0,1);//1 x 3 x x x x
//        segTree.pt(segTree,6);
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N,0, 0));//1
//
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 0, 2));//4
//
//        segTree.updateSetSum(segTree.root,0,segTree.N,1,1,2);//1 2 3 x x x x
//        segTree.pt(segTree,6);
//        System.out.println(segTree.querySetSum(segTree.root, 0, segTree.N, 0, 4));//6
//
//        segTree.updateSetSum(segTree.root,0,segTree.N,3,3,4);//1 2 3 4 x x x
//        segTree.pt(segTree,6);
//        System.out.println(segTree.querySetSum(segTree.root,0,segTree.N,0,4));//10
//
//        segTree.updateSetSum(segTree.root,0,segTree.N,0,4,1);//1 1 1 1 1 x x
//        segTree.pt(segTree,6);
//        System.out.println(segTree.querySetSum(segTree.root,0,segTree.N,0,4));//5
    }

    @Test
    public void testSegTreeDynamic3(){
        SegTreeDynamic segTree = new SegTreeDynamic();
        segTree.updateSetMax(segTree.root,0,segTree.N,2,2,3);//x x 3 x x x x
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 2, 2));//3
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 2, 3));//3
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 1, 2));//3
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 0, 1));//0

        segTree.updateSetMax(segTree.root,0,segTree.N,0,0,1);//1 x 3 x x x x
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N,0, 0));//1

        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 0, 2));//3

        segTree.updateSetMax(segTree.root,0,segTree.N,1,1,2);//1 2 3 x x x x
        System.out.println(segTree.querySetMax(segTree.root, 0, segTree.N, 0, 4));//3

        segTree.updateSetMax(segTree.root,0,segTree.N,3,3,4);//1 2 3 4 x x x
        System.out.println(segTree.querySetMax(segTree.root,0,segTree.N,0,4));//4

        segTree.updateSetMax(segTree.root,0,segTree.N,0,4,1);//1 1 1 1 1 x x
        System.out.println(segTree.querySetMax(segTree.root,0,segTree.N,0,4));//1
    }
    //===
}
